/*
 * JBeagle - a Java toolkit for genetic algorithms.
 * 
 * Copyright (c) 2010 Matthijs Snel
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package jbeagle.core;

import java.util.ArrayList;
import java.util.List;

import org.apache.log4j.Logger;

import jbeagle.core.ops.GeneticOperator;
import jbeagle.core.select.Selector;


/**
 * The core class implementing the genetic algorithm routine.
 * <p>
 * A genetic algorithm operates on a {@link Population} of {@link Indvidual}s that represent
 * solutions to the problem at hand. The "goodness" of individuals, i.e. their proximity
 * to the optimal solution to the problem, is indicated by a fitness score that is stored
 * on the {@code Individual}. The fitness score is assigned by a {@link FitnessFunction}.
 * A developer will most likely have to provide her own implementation of the {@code FitnessFunction}
 * interface as these evaluation functions are highly problem-dependent. However, a number of
 * example fitness functions have been provided in the {@link jbeagle.examples} package. The
 * {@link #setFitnessFunction(FitnessFunction)} method should be used to provide the fitness function.
 * <p>
 * The principle of a genetic algorithm is that it works according to the principles of
 * natural selection, i.e. good ("fit") individuals have a higher chance of reproducing than
 * less fit individuals. By repeatedly selecting and interbreeding fit individuals, the hope
 * is that eventually (a) satisfactory solution(s) to the problem will be reached.
 * <p>
 * Individuals are selected by a {@link Selector} for reproduction. A {@code Selector} takes
 * the current population, selects individuals according to their fitness score, and returns
 * an "intermediate" population that will be used for breeding. A number of common {@code Selector}
 * implementations are provided in the {@link jbeagle.core.select} package. The
 * {@link #setSelectionMethod(Selector)} method should be used to provide a {@code Selector}.
 * <p>
 * The "breeding" phase consists of applying a number of {@link GeneticOperator}s to the
 * intermediate population. The most common operators are the mutation (represented by {@link Mutator})
 * and crossover (represented by {@link CrossoverOperator}) operators. A number of common {@code Mutator}
 * and {@code CrossoverOperator} implementations are provided in the {@link jbeagle.core.ops} package.
 * Genetic operators can be added by using the {@link #addOperator(GeneticOperator)} method.
 * Operators will be applied in the order in which they have been added to the {@code GeneticAlgorithm}.
 * <p>
 * After breeding, the resulting population is evaluated for fitness and the whole process
 * repeats itself, until a {@link StopCondition} has been satisfied.
 * <p>
 * Since {@code GeneticAlgorithm} implements {@code Runnable}, it can easily be run in a separate
 * thread, which among others allows for pausing the GA and polling for intermediate results.
 * <p>
 * Results can be obtained by calling {@link #getResults()}, which returns a {@code List} of
 * arrays. Each array contains two {@code double} values; the first corresponds to the average
 * population fitness, the second to the fitness of the best individual. The list index
 * corresponds to the GA generation: results for the first generation are at index 0, for the
 * 100th generation at index 99, etc.
 * 
 * @author Matthijs Snel
 * @see jbeagle.core.Population
 * @see jbeagle.core.Individual
 * @see jbeagle.core.FitnessFunction
 * @see jbeagle.core.select.Selector
 * @see jbeagle.core.ops.GeneticOperator
 * @see jbeagle.core.ops.Mutator
 * @see jbeagle.core.ops.CrossoverOperator
 * @see jbeagle.core.GeneticAlgorithm.StopCondition
 * @see java.lang.Runnable
 * @since 0.1	
 */

public class GeneticAlgorithm<I extends Individual<G>, G> implements Runnable {

	static Logger log = Logger.getLogger(GeneticAlgorithm.class);
	
	protected FitnessFunction<I, G> fitnessf;
	protected Population<I, G> pop;
	protected ArrayList<GeneticOperator<I, G>> operators;
	protected Selector selector;
	protected StopCondition stopCriterion;
	
	protected ArrayList<double[]> results;
	
	private int currGeneration;
	
	private List<FitnessChangeListener> fitnessListeners;
	
	public GeneticAlgorithm() {
		currGeneration = 0;
		operators = new ArrayList<GeneticOperator<I, G>>(2);
		results = new ArrayList<double[]>(200);
		fitnessListeners = new ArrayList<FitnessChangeListener>();
	}
	
	public void run() {
		log.info("Genetic algorithm starting.");
		
		if( stopCriterion == null ) {
			log.error("A StopCondition must be provided before running the GA.");
			throw new IllegalStateException("A StopCondition must be provided before running the GA.");
		}
		
		evaluateFitness();
		
		while (!isFinished()) {		
			nextGeneration();
			evaluateFitness();
		}
		log.info("Genetic algorithm finished.");
	}
	
	public void addOperator( GeneticOperator<I, G> op ) {
		operators.add(op);
	}
	
	public int getCurrentGeneration() {
		return currGeneration;
	}
	
	public FitnessFunction<I, G> getFitnessFunction() {
		return fitnessf;
	}
	
	public Selector getSelectionMethod() {
		return selector;
	}
	
	@SuppressWarnings("unchecked")
	/**
	 * Returns a shallow copy of the list of current genetic operators of the GA. I.e., modifications
	 * on the returned list will not be reflected in the GA, but modifications on the operators
	 * contained in the list will.
	 */
	public List<GeneticOperator<I, G>> getOperators() {
		return (List<GeneticOperator<I, G>>) operators.clone();
	}
	
	public Population<I, G> getPopulation() {
		return pop;
	}
	
	public List<double[]> getResults() {
		return results;
	}
	
	/**
	 * Empties current results and zeroes generation counter. Does NOT re-initialise the
	 * population.
	 */
	public void reset() {
		results.clear();
		currGeneration = 0;
	}
	
	public void setFitnessFunction( FitnessFunction<I, G> f ) {
		fitnessf = f;
	}
	
	public void setPopulation( Population<I, G> p ) {
		pop = p;
	}
	
	public void setSelectionMethod( Selector method ) {
		selector = method;
	}
	
	public void setStopCondition( StopCondition sc ) {
		stopCriterion = sc;
	}
	
	protected void updateResults() {
		double result[] = new double[2];
		result[0] = pop.getAvgFitness();
		result[1] = pop.getFittest().getFitness();
		results.add(result);
	}
	
	//// Methods for incrementally advancing the GA ////
	/**
	 * Evaluate fitness, update population and results. Returns true if GA is finished according to specified stopcondition.
	 */
	public boolean evaluateFitness() {
		fitnessf.evaluate(pop);
		pop.updateFitness();
		updateResults();
		fireFitnessChangeEvent();
		return isFinished();
	}
	
	/**
	 * Applies selection mechanism and genetic operators and generates next generation.
	 */
	public void nextGeneration() {
		pop = selector.apply(pop);
		for ( GeneticOperator<I, G> op : operators )
			pop = op.apply( pop );
		currGeneration++;
	}
	
	public boolean isFinished() {
		return stopCriterion.satisfied();
	}
	
	public void addFitnessChangeListener(FitnessChangeListener l) {
		fitnessListeners.add(l);
	}
	
	protected void fireFitnessChangeEvent() {
		FitnessChangeEvent e = new FitnessChangeEvent(pop, currGeneration, isFinished());
		for ( FitnessChangeListener l : fitnessListeners )
			l.fitnessChanged(e);
	}
	
	public class StopCondition {
		/**
		 * Runs the GA until the best individual in the population equals or exceeds the fitness
		 * specified in the constructor.
		 */
		public static final int SOLUTION_FOUND = 1;
		
		/**
		 * Runs the GA until the average population fitness equals or exceeds the fitness
		 * specified in the constructor.
		 */
		public static final int	FITNESS_REACHED = 2;
		
		/**
		 * Runs the GA until the the maximum number of generations specified in the constructor
		 * have been reached.
		 */
		public static final int	MAX_GEN = 3;
		
		protected int type, maxGen;
		protected double fitness;
		
		/**
		 * Default constructor. Runs the GA until the best individual in the population
		 * has a fitness of 1.0, or until the GA has run for {@code Integer.MAX_VALUE} - 1 generations. Use
		 * of this constructor is therefore not recommended.
		 */
		public StopCondition() {
			this( SOLUTION_FOUND, 1.0);
		}
		
		/**
		 * Runs the GA for the number of generations specified by maxGen.
		 * 
		 * @param maxGen the number of generations for which the GA should run.
		 */
		public StopCondition( int maxGen ) {
			this( MAX_GEN, maxGen, 0 );
		}
		
		/**
		 * 
		 * @param type
		 * @param fitness
		 */
		public StopCondition( int type, double fitness ) {
			this( type, Integer.MAX_VALUE, fitness );
		}
		
		/**
		 * Recommended constructor. Allows to run the GA until the best or average
		 * fitness satisfy the fitness criterion, OR until a maximum number of
		 * generations have been reached.
		 * 
		 * @param type The stop condition type ({@code SOLUTION_FOUND} or
		 * {@code FITNESS_REACHED}, {@code MAX_GEN} doesn't make sense here)
		 * @param maxGen the maximum number of generations that the GA is allowed to run for
		 * @param fitness the fitness level the best or average fitness should reach
		 */
		public StopCondition( int type, int maxGen, double fitness ) {
			this.type = type;
			this.maxGen = maxGen-1;
			this.fitness = fitness;
		}
		
		/**
		 * Checks whether the specified stopping condition(s) have been satisfied.
		 * 
		 * @return true if the conditions have been satisfied. This will cause the GA to stop.
		 */
		public boolean satisfied() {
			if ( currGeneration >= maxGen )
				return true;
			
			if( type != MAX_GEN ) {
				double toCheck = (type == SOLUTION_FOUND ? pop.getFittest().getFitness() :
									pop.getAvgFitness());
				return toCheck >= fitness;
			}
			return false;
		}
		
		/**
		 * 
		 * @return the fitness level that should be reached before the GA stops
		 */
		public double getFitness() {
			return fitness;
		}

		/**
		 * 
		 * @param fitness the fitness level that should be reached before the GA stops
		 */
		public void setFitness(double fitness) {
			this.fitness = fitness;
		}

		/**
		 * 
		 * @return the type of stop condition
		 */
		public int getType() {
			return type;
		}
	}
}
